{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Level Order Traversal II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: levelOrderBottom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的层序遍历 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> ，返回其节点值 <strong>自底向上的层序遍历</strong> 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg\" style=\"width: 277px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>[[15,7],[9,20],[3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[[1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[0, 2000]</code> 内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-level-order-traversal-ii](https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-level-order-traversal-ii](https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[1]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = collections.deque([root])\n",
    "        result = []\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                level.append(queue[0].val)\n",
    "                if queue[0].left:\n",
    "                    queue.append(queue[0].left)\n",
    "                if queue[0].right:\n",
    "                    queue.append(queue[0].right)\n",
    "                queue.popleft()\n",
    "            result.append(level)\n",
    "        return result[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        \n",
    "        node = [root]\n",
    "        a = []\n",
    "        #p=[]\n",
    "        if root is None:\n",
    "            return a\n",
    "        while(node):\n",
    "            b = []#存储每一层\n",
    "            d = []\n",
    "            for i in node:#访问每一层\n",
    "                d.append(i.val)\n",
    "                if i.left != None:\n",
    "                    b.append(i.left)\n",
    "                if i.right != None:\n",
    "                    b.append(i.right)\n",
    "            node = b\n",
    "            a.append(d)\n",
    "        a.reverse()\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        ret, queue = [], []\n",
    "        if root:\n",
    "            queue.append((root, 0))\n",
    "        cur_depth, cur_level = -1, None\n",
    "        while queue:\n",
    "            node, depth = queue.pop(0)\n",
    "            if depth != cur_depth:\n",
    "                if cur_level:\n",
    "                    ret.insert(0, cur_level)\n",
    "                cur_level = []\n",
    "                cur_depth = depth\n",
    "            cur_level.append(node.val)\n",
    "            if node.left:\n",
    "                queue.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, depth + 1))\n",
    "        if cur_level:\n",
    "            ret.insert(0, cur_level)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        level_order = []\n",
    "        out = []\n",
    "        level_order.insert(0,[root])\n",
    "        while level_order:\n",
    "            nodes = level_order.pop()\n",
    "            level = [n.val for n in nodes]\n",
    "            out.insert(0,level)\n",
    "            new_level = []\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    new_level.append(node.left)\n",
    "                if node.right:\n",
    "                    new_level.append(node.right)\n",
    "            if len(new_level)>0:\n",
    "                level_order.append(new_level)\n",
    "            \n",
    "            \n",
    "        return out\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        level_order = []\n",
    "        out = []\n",
    "        level_order.insert(0,[root])\n",
    "        while level_order:\n",
    "            nodes = level_order.pop()\n",
    "            level = [n.val for n in nodes]\n",
    "            out.insert(0,level)\n",
    "            new_level = []\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    new_level.append(node.left)\n",
    "                if node.right:\n",
    "                    new_level.append(node.right)\n",
    "            if len(new_level)>0:\n",
    "                level_order.append(new_level)\n",
    "            \n",
    "            \n",
    "        return out\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        self.dfs(root, 0, res)\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, root, level, res):\n",
    "        if root:\n",
    "            if len(res) < level + 1:\n",
    "                res.insert(0, [])\n",
    "            res[-level-1].append(root.val)\n",
    "            self.dfs(root.left, level + 1, res)\n",
    "            self.dfs(root.right, level + 1, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=107 lang=python3\n",
    "#\n",
    "# [107] 二叉树的层次遍历 II\n",
    "#\n",
    "# https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (58.18%)\n",
    "# Total Accepted:    9.4K\n",
    "# Total Submissions: 16.1K\n",
    "# Testcase Example:  '[3,9,20,null,null,15,7]'\n",
    "#\n",
    "# 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）\n",
    "# \n",
    "# 例如：\n",
    "# 给定二叉树 [3,9,20,null,null,15,7],\n",
    "# \n",
    "# ⁠   3\n",
    "# ⁠  / \\\n",
    "# ⁠ 9  20\n",
    "# ⁠   /  \\\n",
    "# ⁠  15   7\n",
    "# \n",
    "# \n",
    "# 返回其自底向上的层次遍历为：\n",
    "# \n",
    "# [\n",
    "# ⁠ [15,7],\n",
    "# ⁠ [9,20],\n",
    "# ⁠ [3]\n",
    "# ]\n",
    "# \n",
    "# \n",
    "#\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "\n",
    "    def levelOrderBottom(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        self.res = []\n",
    "\n",
    "        self.print_node(root)\n",
    "\n",
    "        return self.res[::-1]\n",
    "\n",
    "    def print_node(self, node:'TreeNode', idx=0) -> 'TreeNode':\n",
    "        # print(\"## {} ##\".format(node.val))\n",
    "\n",
    "        if idx >= len(self.res):\n",
    "            self.res.append([])\n",
    "\n",
    "        vals = self.res[idx]\n",
    "\n",
    "        vals.append(node.val)\n",
    "\n",
    "        if not node.left and not node.right: \n",
    "            return\n",
    "\n",
    "        # self.res.append(vals)\n",
    "\n",
    "        if node.left:\n",
    "            self.print_node(node.left, idx+1)\n",
    "            \n",
    "        if node.right:\n",
    "            self.print_node(node.right, idx+1)\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def dfs(node,level,res):\n",
    "            if not node:\n",
    "                return \n",
    "            if len(res) < level:\n",
    "                res.append([])\n",
    "            res[level-1].append(node.val)\n",
    "            dfs(node.left,level+1,res)\n",
    "            dfs(node.right,level+1,res)\n",
    "        res = []\n",
    "        dfs(root,1,res)\n",
    "        return res[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def pr(self, dq, k, depth, dk, dpdq):\n",
    "        if dq:\n",
    "            x = dq.popleft()\n",
    "            print(x.val)\n",
    "            k.append(x.val)\n",
    "            dk.append(dpdq.popleft())\n",
    "        if x.left:\n",
    "            dq.append(x.left)\n",
    "            dpdq.append(dk[-1] + 1)\n",
    "        if x.right:    \n",
    "            dq.append(x.right)\n",
    "            dpdq.append(dk[-1] + 1)\n",
    "        if not dq:\n",
    "            return\n",
    "        self.pr(dq, k, depth, dk, dpdq)\n",
    "    \n",
    "    def levelOrderBottom(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        dq = deque()\n",
    "        dpdq = deque()\n",
    "        dpdq.append(0)\n",
    "        dq.append(root)\n",
    "        k = []\n",
    "        dk = []\n",
    "        self.pr(dq, k, 0, dk, dpdq)\n",
    "        print(k)\n",
    "        print(dk)\n",
    "        s = max(dk)\n",
    "        r = []\n",
    "        for i in range(s + 1):\n",
    "            ind = [j for j in range(len(dk)) if dk[j] == i]\n",
    "            r.append([k[e] for e in ind])\n",
    "        r.reverse()\n",
    "        print(r)\n",
    "        return(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=107 lang=python3\n",
    "#\n",
    "# [107] 二叉树的层次遍历 II\n",
    "#\n",
    "# https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (58.09%)\n",
    "# Total Accepted:    9.1K\n",
    "# Total Submissions: 15.6K\n",
    "# Testcase Example:  '[3,9,20,null,null,15,7]'\n",
    "#\n",
    "# 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）\n",
    "#\n",
    "# 例如：\n",
    "# 给定二叉树 [3,9,20,null,null,15,7],\n",
    "#\n",
    "# ⁠   3\n",
    "# ⁠  / \\\n",
    "# ⁠ 9  20\n",
    "# ⁠   /  \\\n",
    "# ⁠  15   7\n",
    "#\n",
    "#\n",
    "# 返回其自底向上的层次遍历为：\n",
    "#\n",
    "# [\n",
    "# ⁠ [15,7],\n",
    "# ⁠ [9,20],\n",
    "# ⁠ [3]\n",
    "# ]\n",
    "#\n",
    "#\n",
    "#\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        from copy import deepcopy\n",
    "\n",
    "        inn = []\n",
    "        next_inn = [root]\n",
    "        res = []\n",
    "\n",
    "        while inn or next_inn:\n",
    "            inn = deepcopy(next_inn)\n",
    "            next_inn = []\n",
    "            vals = [] \n",
    "            while inn:\n",
    "                node = inn.pop(0)\n",
    "                if not node:\n",
    "                    return vals\n",
    "                \n",
    "                vals.append(node.val)\n",
    "                if node.left:\n",
    "                    next_inn.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    next_inn.append(node.right)\n",
    "            res.append(vals)\n",
    "        \n",
    "        return res[::-1]\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root == None:\n",
    "            return []\n",
    "        anslist = [[root]]\n",
    "        while True:\n",
    "            mylist = []\n",
    "            for i in anslist[-1]:\n",
    "                if i.left != None:\n",
    "                    mylist.append(i.left)\n",
    "                if i.right != None:\n",
    "                    mylist.append(i.right)\n",
    "            if mylist == []:\n",
    "                break\n",
    "            else:\n",
    "                anslist.append(mylist)\n",
    "        ans = []\n",
    "        for i in anslist:\n",
    "            mylist = []\n",
    "            for j in i:\n",
    "                mylist.append(j.val)\n",
    "            ans.append(mylist)\n",
    "        return ans[-1::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        queue = []\n",
    "        cur = [root]\n",
    "        while cur:\n",
    "            curr_layer = []\n",
    "            next_layer = []\n",
    "            for node in cur:\n",
    "                if node:\n",
    "                    curr_layer.append(node.val)\n",
    "                    next_layer.extend([node.left,node.right])\n",
    "            if curr_layer:\n",
    "                queue.insert(0,curr_layer)\n",
    "            cur = next_layer\n",
    "        return queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef levelOrderBottom(self,root):\n",
    "\t\tans=[]\n",
    "\t\tif root:\n",
    "\t\t\tqueue=[root]\n",
    "\t\t\twhile queue:\n",
    "\t\t\t\tnew_queue=[]\n",
    "\t\t\t\tans.insert(0,list())\n",
    "\t\t\t\tfor i in queue:\n",
    "\t\t\t\t\tans[0].append(i.val)\n",
    "\t\t\t\t\tfor j in (i.left,i.right):\n",
    "\t\t\t\t\t\tif j:\n",
    "\t\t\t\t\t\t\tnew_queue.append(j)\n",
    "\t\t\t\tqueue=new_queue\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        stack = deque()\n",
    "        stack.append(root)\n",
    "        while stack:\n",
    "            tmp = []\n",
    "            n = len(stack)\n",
    "            for i in range(n):\n",
    "                node = stack.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            if tmp:\n",
    "                res.insert(0,tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        tree_res, level = [], 0\n",
    "        if not root:\n",
    "            return []\n",
    "        tree_res.append([root])\n",
    "        while level < len(tree_res):\n",
    "            level_res = []\n",
    "            for tree in tree_res[0]:\n",
    "                if tree.left:\n",
    "                    level_res.append(tree.left)\n",
    "                if tree.right:\n",
    "                    level_res.append(tree.right)\n",
    "            if level_res:\n",
    "                tree_res = [level_res] + tree_res\n",
    "            level += 1\n",
    "        res = []\n",
    "        for level in tree_res:\n",
    "            level_val = []\n",
    "            for tree in level:\n",
    "                level_val.append(tree.val)\n",
    "            res.append(level_val)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        visited, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                q = queue.popleft()\n",
    "                level.append(q.val)\n",
    "                if q.left: queue.append(q.left)\n",
    "                if q.right: queue.append(q.right)\n",
    "            visited.insert(0,level)\n",
    "        return visited\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        queue = [root]\n",
    "        result = []\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            temp = []\n",
    "            for i in range(n):\n",
    "                node = queue.pop(0)\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            result.append(temp)\n",
    "        return list(reversed(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        queue = []\n",
    "        if not root:\n",
    "            return []\n",
    "        queue.append([root])\n",
    "        result = [[root.val]]\n",
    "        while queue:\n",
    "            child_node = []\n",
    "            child_list = []\n",
    "            for node in queue.pop(0):\n",
    "                if node.left:\n",
    "                    child_node.append(node.left)\n",
    "                    child_list.append(node.left.val)\n",
    "                if node.right:\n",
    "                    child_node.append(node.right)\n",
    "                    child_list.append(node.right.val)\n",
    "            if child_node:\n",
    "                    queue.append(child_node)\n",
    "            if child_list:\n",
    "                    result.append(child_list)\n",
    "        result.reverse()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root) -> List[List[int]]:\n",
    "        res = []\n",
    "        cur_layer_node = [root]\n",
    "        while cur_layer_node:\n",
    "            cur_layer_val = []\n",
    "            next_layer_node = []\n",
    "            for node in cur_layer_node:\n",
    "                if node:\n",
    "                    cur_layer_val.append(node.val)\n",
    "                    # 同层从左到右\n",
    "                    next_layer_node.extend([node.left, node.right])\n",
    "            if cur_layer_val:\n",
    "                # 插入到list首部则为倒着的层序遍历，append到尾部则为层序遍历,\n",
    "                res.insert(0, cur_layer_val)\n",
    "            cur_layer_node = next_layer_node\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.record = dict()\n",
    "\n",
    "    def traverse(self, node: TreeNode, deep: int):\n",
    "        if node is None: return deep\n",
    "        deep += 1\n",
    "        if str(deep) in self.record:\n",
    "            self.record[str(deep)].append(node.val)\n",
    "        else:\n",
    "            self.record[str(deep)] = [node.val, ]\n",
    "        self.traverse(node.left, deep)\n",
    "        self.traverse(node.right, deep)\n",
    "\n",
    "    def levelOrderBottom(self, root: TreeNode) -> list:\n",
    "        self.traverse(root, 0)\n",
    "        keys = sorted(self.record.keys(), key=lambda x:int(x), reverse=True)\n",
    "        result = []\n",
    "        for key in keys:\n",
    "            result.append(self.record[key])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(root, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            if len(res)<depth+1:\n",
    "                res.append([])\n",
    "            res[depth].append(root.val)\n",
    "            dfs(root.left, depth+1)\n",
    "            dfs(root.right, depth+1)\n",
    "        dfs(root,0)\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = [[root]]\n",
    "        while stack[-1]:\n",
    "            nodes = stack[-1]\n",
    "            new_nodes = []\n",
    "            for node in nodes:\n",
    "                if node.left:\n",
    "                    new_nodes.append(node.left)\n",
    "                if node.right:\n",
    "                    new_nodes.append(node.right)\n",
    "            stack.append(new_nodes)\n",
    "        res = []\n",
    "        for nodes in reversed(stack):\n",
    "            if nodes: res.append([node.val for node in nodes])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = deque([])\n",
    "        if root is None:\n",
    "            return list(res)\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            tmp = []\n",
    "            for i in range(l):\n",
    "                cur = q.popleft()\n",
    "                tmp.append(cur.val)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            res.insert(0, tmp)\n",
    "        return list(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        self.result = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            curr_len = len(queue)\n",
    "            curr_level = []\n",
    "            for _ in range(curr_len):\n",
    "                curr_node = queue.pop(0)\n",
    "                curr_level.append(curr_node.val)\n",
    "                if curr_node.left:\n",
    "                    queue.append(curr_node.left)\n",
    "                if curr_node.right:\n",
    "                    queue.append(curr_node.right)\n",
    "            self.result.insert(0, curr_level)\n",
    "        \n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        results=[]\n",
    "        if not root:return results\n",
    "        from collections import deque\n",
    "        que=deque([root])\n",
    "        while que:\n",
    "            result=[]\n",
    "            for _ in range(len(que)):\n",
    "                cur=que.popleft()\n",
    "                result.append(cur.val)\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "            results.append(result)\n",
    "        results.reverse()\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        from collections import deque\n",
    "        q = deque()\n",
    "        if root:\n",
    "            q.append(root)\n",
    "        ans = []\n",
    "        while len(q)>0:\n",
    "            l = len(q)\n",
    "            tmp = []\n",
    "            while l>0:\n",
    "                node = q.popleft()\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                l -= 1\n",
    "            ans.append(tmp)\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def levelOrderBottom(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        # 用来存放最终结果    \n",
    "        res = []\n",
    "        def dfs(root,index):\n",
    "            if not root:\n",
    "                return\n",
    "            # 如果index大于res大小，说明这一层没有对应的集合，需要新创建    \n",
    "            if index>len(res):\n",
    "                res.append([])\n",
    "            # 将当前层的元素直接放到对应层的末尾即可    \n",
    "            res[index-1].append(root.val)\n",
    "            # 继续遍历左右节点，同时将层高+1\n",
    "            dfs(root.left,index+1)\n",
    "            dfs(root.right,index+1)\n",
    "        dfs(root,1)\n",
    "        return res[::-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def helper(root:Optional[TreeNode], depth: int, ans: List[List[int]]) -> None:\n",
    "            if not root: return \n",
    "            if depth <len(ans): ans[depth].append(root.val)\n",
    "            else: ans.append([root.val])\n",
    "            helper(root.left, depth+1, ans)\n",
    "            helper(root.right, depth+1, ans)\n",
    "\n",
    "        ans = []\n",
    "        helper(root, 0, ans)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            res.append([node.val for node in queue])\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "            queue = tmp\n",
    "        return res[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        que = collections.deque()\n",
    "        res = collections.deque()\n",
    "        que.append(root)\n",
    "        while que:\n",
    "            ll = len(que)\n",
    "            tmp = []\n",
    "            for i in range(ll):\n",
    "                node = que.popleft()\n",
    "                if node.left is not None:\n",
    "                    que.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    que.append(node.right)\n",
    "                tmp.append(node.val)\n",
    "            res.appendleft(tmp)\n",
    "        return list(res)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        nqueue = [[root, 0]]\n",
    "        result = []\n",
    "        while len(nqueue)!=0:\n",
    "            node, depth = nqueue.pop(-1)\n",
    "            if depth==len(result):\n",
    "                result.append([])\n",
    "            result[depth].append(node.val)\n",
    "            if node.right is not None:\n",
    "                nqueue.append([node.right, depth+1])\n",
    "            if node.left is not None:\n",
    "                nqueue.append([node.left, depth+1])\n",
    "        return result[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # DFS\n",
    "    # N is the size of tree\n",
    "    # H is the height of tree\n",
    "    # Time Complexity: O(N)\n",
    "    # Space Complexity: O(H)\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        r = []\n",
    "        if root is None:\n",
    "            return r\n",
    "        self.c(root,r,0)\n",
    "        r.reverse()\n",
    "        return r\n",
    "    def c(self,node,r,l):\n",
    "        if node is None:\n",
    "            return\n",
    "        if l>len(r)-1:\n",
    "            r.append([])\n",
    "        r[l].append(node.val)\n",
    "\n",
    "        if node.left!=None:\n",
    "            self.c(node.left,r,l+1)\n",
    "        if node.right!=None:\n",
    "            self.c(node.right,r,l+1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        def f(root, n, ar):\n",
    "            if not root:\n",
    "                return\n",
    "            if len(ar) == n:\n",
    "                ar.append([])\n",
    "            ar[n].append(root.val)\n",
    "            f(root.left, n + 1, ar)\n",
    "            f(root.right, n + 1, ar)\n",
    "        ans = []\n",
    "        f(root, 0, ans)\n",
    "        return ans[::-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
